const { defaultCompare, Compare } = require('../util');
const { Node } = require('./models/node');

class BinarySearchTree {
  constructor(compareFn = defaultCompare) {
    this.compareFn = compareFn; // 用来比较节点值
    this.root = null; // Node类型的根节点
  }

  /**
   * 向二叉搜索树中插入一个新的键
   * @param {*} key
   */
  insert(key) {
    if (this.root === null) {
      this.root = new Node(key);
    } else {
      this.insertNode(this.root, key);
    }
  }

  insertNode(node, key) {
    if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
      if (node.left === null) {
        node.left = new Node(key);
      } else {
        this.insertNode(node.left, key);
      }
    }
    if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {
      // eslint-disable-next-line no-lonely-if
      if (node.right === null) {
        node.right = new Node(key);
      } else {
        this.insertNode(node.right, key);
      }
    }
  }

  /**
   * 中序遍历
   * @param {*} callback 定义遍历到的每个节点进行的操作
   */
  inOrderTraverse(callback) {
    this.inOrderTraverseNode(this.root, callback); // 辅助方法，接收一个节点和对应的回调函数作为参数
  }

  inOrderTraverseNode(node, callback) {
    // 检查以参数形式传入的节点是否为null，停止递归继续执行的判断条件，递归算法的基准条件。
    if (node != null) {
      this.inOrderTraverseNode(node.left, callback); // 递归调用相同的函数访问左侧子节点
      callback(node.key); // 对根节点进行一些操作（callback）
      this.inOrderTraverseNode(node.right, callback); // 访问右侧子节点
    }
  }

  /**
   * 先序遍历
   * 先序遍历的一种应用是打印一个结构化的文档
   */
  preOrderTraverse(callback) {
    this.preOrderTraverseNode(this.root, callback);
  }

  preOrderTraverseNode(node, callback) {
    if (node != null) {
      callback(node.key);
      this.preOrderTraverseNode(node.left, callback);
      this.preOrderTraverseNode(node.right, callback);
    }
  }

  /**
   * 后序遍历
   */
  postOrderTraverse(callback) {
    this.postOrderTraverseNode(this.root, callback);
  }

  postOrderTraverseNode(node, callback) {
    if (node != null) {
      this.postOrderTraverseNode(node.left, callback);
      this.postOrderTraverseNode(node.right, callback);
      callback(node.key);
    }
  }

  min() {
    return this.minNode(this.root);
  }

  /**
   * 找到一棵树或其子树中最小的键
   */
  minNode(node) {
    let current = node;
    while (current != null && current.left != null) {
      current = current.left;
    }
    return current;
  }

  max() {
    return this.maxNode(this.root);
  }

  /**
   * 找到一棵树或其子树中最大的键
   */
  maxNode(node) {
    let current = node;
    while (current != null && current.right != null) {
      current = current.right;
    }
    return current;
  }

  search(key) {
    return this.searchNode(this.root, key); // 使用辅助方法
  }

  searchNode(node, key) {
    // 不是null或undefined
    if (node == null) {
      return false;
    }
    if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
      return this.searchNode(node.left, key);
    }
    if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {
      return this.searchNode(node.right, key);
    }
    return true;
  }

  /**
   * 移除一个节点
   */
  move(key) {
    this.root = this.removeNode(this.root, key); // root被赋值removeNode方法的返回值
  }

  /**
   * removeNode方法的复杂之处在于我们要处理不同的运行场景
   * 当然也同样因为它是通过递归实现的
   */
  removeNode(node, key) {
    // {2} 正在检测的节点为null，说明键不存在，返回null
    if (node == null) {
      return null;
    }
    // {3}
    if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
      node.left = this.removeNode(node.left, key); // {4} 沿着树的左边找到下一个节点
      return node; // {5}
    }
    // {6}
    if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {
      node.right = this.removeNode(node.right, key); // {7} 沿着树的右边找到下一个节点
      return node; // {8}
    }
    // 键等于node.key
    // 第一种情况
    // {9}
    if (node.left == null && node.right == null) {
      node = null; // {10} 给这个节点赋予null值来移除它
      return node; // {11} 这个节点没有任何子节点，但是有一个父节点，需要通过返回null来讲对应的父节点指针赋予null值
    }
    // 第二种情况
    // {12}
    if (node.left == null) {
      node = node.right; // {13}
      return node; // {14}
    }
    // {15}
    if (node.right == null) {
      node = node.left; // {16}
      return node; // {17}
    }
    // 第三种情况
    const aux = this.minNode(node.right); // {18}
    node.key = aux.key; // {19}
    node.right = this.removeNode(node.right, aux.key); // {20}
    return node; // {21}
  }
}

exports.BinarySearchTree = BinarySearchTree;
